In storing a secret such as a password, personal information, and encryption key information, there is a threat of the loss or destruction, and a threat of the stealing, of the secret. The creation of a copy of a secret, though effective against loss, increases the threat of stealing.
To solve this problem, attention has been paid to the (k,n) threshold secret sharing scheme proposed by Shamir (Non-Patent Document 3).
In the (k, n) threshold secret sharing scheme, a secret is encoded into n shares where k is a threshold, and n is the number of divisions. This scheme is characterized in that a secret can be reconstructed by any k or more shares out of n shares, but not by (k−1) or fewer shares.
In the scheme described in Non-Patent Document 3, a finite field GF(p) for p that is a prime number or a power of a prime number is used as a data set of secrets, and random points (x1, f(x1)), . . . , (xn, f(xn)) on a (k−1) degree polynomial f(x) on GF(p), which includes the secret S in a constant term, are generated as shares.
If k shares are given, the (k−1) degree polynomial f(x) may be reconstructed uniquely. In this case, the secret S may be reconstructed as the value of f(0), that is, as the value of the constant term of the function f(x).
In addition, because the (k−1) degree polynomial cannot be determined uniquely from (k−1) or fewer shares, the secret S is not leaked.
Therefore, when the (k, n) threshold secret sharing scheme is used, the secret is not leaked even if (k−1) or fewer shares are stolen, and the secret may be reconstructed even if up to (n−k) shares are destroyed.
Now, assume that shares have been created and assigned correctly in the (k, n) threshold secret sharing scheme. In this case, a user who wants to reconstruct the secret tries to collect the shares from other users having the shares.
However, not all other users who are requested to send shares always send the shares without forging them (in the description below, a user who is a participant of the secret sharing scheme and sends a forged share is called a cheater). The value reconstructed based on a forged share may be a value different from the original value of the secret.
It is therefore preferable to be able detect with a high probability that, among those used for reconstruction, there is a share that is forged in order to make the value of the reconstructed secret different from the original value.
To solve this problem, Non-Patent Documents 1 and 2 describe the following methods.
The method described in Non-Patent Document 1 is a (k,n) threshold secret sharing scheme and, if the cheating detection probability is (1−ε) and the secret is selected from a set of s elements, the shares form a set of about s/ε elements.
This scheme ensures security provided that the secret is selected according to the uniform distribution. This cheating detection scheme satisfies the condition described above even if up to (k−1) shares are forged when k shares are input.
Actually, however, the secret is not always selected according to the uniform distribution and so there is a need for a method not requiring this condition.
On the other hand, Non-Patent Document 2 proposes a scheme that is secure even when the secret is selected according to any distribution. This scheme is a (k, n) threshold secret sharing scheme and, if the cheating detection probability is (1−ε), the shares form a set of s/ε2 elements.
This cheating detection scheme satisfies the condition described above even if up to (k−1) shares are forged when k shares are input.
The secret sharing schemes described in Non-Patent Documents 1 and 2 are called a “cheating detectable secret sharing scheme”. The two methods described above are a scheme in which exactly as many shares as thresholds are used to detect cheating.
Non-Patent Document 6 describes a method for detecting cheating using more shares than thresholds, and it is known that the scheme is very efficient. However, this method requires (k+2u) shares where u is the number of forged shares.
Several methods other than that described in Non-Patent Document 6 are also proposed as a scheme that uses more than k shares to detect cheating. However, those methods are designed not only for detecting cheating but also for special purposes, for example, for identifying altered shared information (may be termed “forged shares”) and therefore they are not always efficient.
It is also known that a message transmission method may be configured using the “cheating detectable secret sharing scheme”.
The message transmission method refers to a transmission method that, when there are n channels between a transmission device and a reception device, the following conditions are satisfied even if the information flowing through up to (k−1) channels is forged and there are cheaters who know the information: (1) the reception device can transmit, with extremely high probability, messages that the transmission device sends; (2) the reception device does not receive the value of a message other than that the transmission device sends; and (3) a cheater cannot estimate a message that the transmission device sends. In the description below, k is called the number of assumed cheating channels.
Such a message transmission method may or may not be configured depending upon the relation between the value of k and the value of n, and various schemes are proposed.
In the present invention, a one-round transmission scheme is assumed in which data may be sent from the transmission device to the reception device only once thorough n channels.
Non-Patent Document 5 describes a transmission method that is efficient when t=(k−1) and n≧3t+1.
Non-Patent Document 4 describes a transmission method for use when 3t+1>n≧2t+1 that is efficient when n=2t+1.
In addition, when n≧3t+1, the method described in Non-Patent Document 4 may be used, but the scheme described in Non-Patent Document 5 is more efficient.
Note that Non-Patent Document 4 describes that the message transmission method cannot be configured when 2t≧n.
The message transmission method described in Non-Patent Document 4 is as follows.
The transmission device generates the shares of a transmission message using the “cheating detectable secret sharing scheme” and sends the shares via channels.
The reception device reconstructs shares, sent via any k channels out of n channels, using the same secret sharing scheme as that of the transmission device and, if the values of all reconstructed messages are the same, outputs the value as the message sent by the transmission device.
That is, the amount of information flowing through each channel depends on the “cheating detectable secret sharing scheme” that is used.
Although transmission via channels has been described, the means that implements the channels may be any means that can separately send multiple pieces of data generated by the transmission device.
Non-Patent Document 1:
W. Ogata, K. Kurosawa, D. R. Stinson: “Optimum Secret Sharing Scheme Secure Against Cheating,” SIAM J.Discrete Math., vol. 20, no. 1, p. 79-95(206)
Non-Patent Document 2:
S. Obana, T. Araki: “Almost Optimum Secret Sharing Schemes Secure Against Cheating for Arbitrary Secret Distribution,” ASIACRYPT, p. 364-379(206)
Non-Patent Document 3:
A. Shamir: “How to share a secret,” Communications of ACM, 22(11), p. 612-613(1979)
Non-Patent Document 4:
K. Kurosawa and K. Suzuki, “Almost Secure (1-Round, n-Channel) Message Transmission Scheme Cryptology ePrint Archive,” http://eprint.iacr.org/207/076
Non-Patent Document 5:
Danny Dolev, Cynthia Dwork, Orli Waarts, Moti Yung: Perfectly Secure Message Transmission FOCS 1990: 36-45
Non-Patent Document 6: R. J. McEliece, D. V. Sarwate: “On Sharing Secrets and Reed-Solomon Codes,” Comm.ACM, 24, p. 583-584(1981)